package TreeTest;

import java.util.ArrayList;

public class Code1_TrieTree {
    public static class TrieTree{
        public int pass;
        public int end;
        public  TrieTree[] nexts;

        public TrieTree(){
            pass=0;
            end=0;
            nexts= new TrieTree[26];
            //0下标代表a  25代表z   值为null则代表没有字符串路过
        }
    }

    public static void main(String[] args) {




        System.out.println("最终结果"+sum(2,3));
    }

    public static int getMax(int[] a){
        int max = Integer.MIN_VALUE;
        for (int x:a){
            if (x>max){
                max = x;
            }
        }
        return max;
    }

    public static long sum (int n, int m) {
        if(n==0 || m==0){
            return 0;
        }
        long res = 0;
        int min = (int) Math.pow(10,(n-1));
        int max = (int) Math.pow(10,n) -1;
        for (int a= min;a<=max ;a++){
            if (getIntSum(a) == m){
                res +=a;
            }
        }
        return res;
    }

    public static int getIntSum(int a){
        int res =0;
        while (a>9){
            res+=a%10;
            a=a/10;
        }
        res +=a;
        return res;
    }

    //统计某字符串在字符串数组中出现的次数
    public static int stringSearch(String str,String[] strings){
        //创建初始节点
        TrieTree first=new TrieTree();
        for (String s: strings){
        TrieTree indexT = first;
            if(s==" "){
                indexT.end++;
            }else {
                for (int a=0;a<s.length();a++){
                    int index = getIndexByStr(s.charAt(a));
                    if (indexT.nexts[index] ==null){
                    indexT.nexts[index]=new TrieTree();
                    }
                    indexT = indexT.nexts[index];
                    indexT.pass++;
                }
                indexT.end++;
            }
        }

        System.out.println("最终"+first.nexts[0]);
        System.out.println("pass:"+first.nexts[0].pass);
        System.out.println("end?:"+first.nexts[0].end);
        //前缀树构建完毕
        ///////////////
        //开始和str对比
        if (str==" "){
            return first.end;
        }
        for (int a=0;a<str.length();a++){
            int index = getIndexByStr(str.charAt(a));
            if (first.nexts[index] == null){
                return -1;
            }
            first = first.nexts[index];
        }
        return first.end;  //此为准确查询
        //此为模糊查询 return first.pass;
    }

    public static int getIndexByStr(char c){
        return (int)c-97;
    }
}
